#
# @lc app=leetcode.cn id=37 lang=python3
# @lcpr version=30204
#
# [37] 解数独
#
# https://leetcode.cn/problems/sudoku-solver/description/
#
# algorithms
# Hard (67.91%)
# Likes:    1846
# Dislikes: 0
# Total Accepted:    259.2K
# Total Submissions: 381.7K
# Testcase Example:  '[["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]'
#
# 编写一个程序，通过填充空格来解决数独问题。
#
# 数独的解法需 遵循如下规则：
#
#
# 数字 1-9 在每一行只能出现一次。
# 数字 1-9 在每一列只能出现一次。
# 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
#
#
# 数独部分空格内已填入了数字，空白格用 '.' 表示。
#
#
#
#
#
#
# 示例 1：
#
# 输入：board =
# [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
#
# 输出：[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
# 解释：输入的数独如上图所示，唯一有效的解决方案如下所示：
#
#
#
#
#
#
# 提示：
#
#
# board.length == 9
# board[i].length == 9
# board[i][j] 是一位数字或者 '.'
# 题目数据 保证 输入数独仅有一个解
#
#
#
#
#
#

# @lcpr-template-start
import copy
from typing import List, Tuple
from typing import Optional
from heapq import heapify, heappop, heappush


# @lcpr-template-end
# @lc code=start
class Solution:
    def backtrace1(self, board: List[List[str]]) -> None:
        row = [[False] * 9 for _ in range(9)]
        col = [[False] * 9 for _ in range(9)]
        box = [[[False] * 9 for _ in range(3)] * 3 for _ in range(3)]
        spaces = []
        self.valid = False

        def dfs(board: List[List[str]], pos: int) -> None:
            if pos == len(spaces):
                self.valid = True
                return
            
            i, j = spaces[pos]
            for digit in range(9):
                if row[i][digit] is False and \
                   col[j][digit] is False and \
                   box[i//3][j//3][digit] is False:
                    
                    row[i][digit] = True
                    col[j][digit] = True
                    box[i//3][j//3][digit] = True

                    board[i][j] = str(digit + 1)
                    dfs(board, pos + 1)

                    row[i][digit] = False
                    col[j][digit] = False
                    box[i//3][j//3][digit] = False

                if self.valid:
                    return
        
        for i in range(9):
            for j in range(9):
                if board[i][j] == ".":
                    spaces.append((i,j))
                else:
                    digit = int(board[i][j]) - 1
                    row[i][digit] = True
                    col[j][digit] = True
                    box[i//3][j//3][digit] = True
        
        dfs(board, 0)

    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        self.backtrace1(board)



# @lc code=end

tests = [[["5", "3", ".", ".", "7", ".", ".", ".", "."],
          ["6", ".", ".", "1", "9", "5", ".", ".", "."],
          [".", "9", "8", ".", ".", ".", ".", "6", "."],
          ["8", ".", ".", ".", "6", ".", ".", ".", "3"],
          ["4", ".", ".", "8", ".", "3", ".", ".", "1"],
          ["7", ".", ".", ".", "2", ".", ".", ".", "6"],
          [".", "6", ".", ".", ".", ".", "2", "8", "."],
          [".", ".", ".", "4", "1", "9", ".", ".", "5"],
          [".", ".", ".", ".", "8", ".", ".", "7", "9"]]]
ans = [[["5", "3", "4", "6", "7", "8", "9", "1", "2"],
        ["6", "7", "2", "1", "9", "5", "3", "4", "8"],
        ["1", "9", "8", "3", "4", "2", "5", "6", "7"],
        ["8", "5", "9", "7", "6", "1", "4", "2", "3"],
        ["4", "2", "6", "8", "5", "3", "7", "9", "1"],
        ["7", "1", "3", "9", "2", "4", "8", "5", "6"],
        ["9", "6", "1", "5", "3", "7", "2", "8", "4"],
        ["2", "8", "7", "4", "1", "9", "6", "3", "5"],
        ["3", "4", "5", "2", "8", "6", "1", "7", "9"]]]
for i,(t,a) in enumerate(zip(tests, ans)):
    tmp_t = copy.deepcopy(t)
    Solution().solveSudoku(t)
    print(f"test case {i+1}:")
    print(f"\ttest =")
    for i in range(9):
        print("\t\t" + str(tmp_t[i]))
    print("\tans =")
    for i in range(9):
        print("\t\t" + str(a[i]))
    print("\tres =")
    for i in range(9):
        print("\t\t" + str(t[i]))
    print(f"\t{a == t}.") 

#
# @lcpr case=start
# [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]\n
# @lcpr case=end

#
